/**
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

 

示例 1：


输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：


输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList1 = function (head) {

    if (!head) return head
    let vals = []

    while (head) {
        vals.push(head.val)
        head = head.next
    }

    vals.sort((a, b) => a - b)


    let newHead = new ListNode(vals[0])
    let currt = newHead

    //  currt.next = new ListNode(vals[2])
    // currt = currt.next
    //  currt.next = new ListNode(vals[3])
    // currt = currt.next
    for (var i = 1; i < vals.length; i++) {
        currt.next = new ListNode(vals[i])
        currt = currt.next
    }

    console.log(newHead)

    return newHead
};



// 这是比较正规的解法
var sortList = function (head) {
    if (!head) return head
    return toSortList(head, null)
};


var toSortList = function (head, tail) {

    if (!head) return null

    //这里是关键点 只有两个节点时返回，使用递归比较两个的大小
    if (head.next === tail) {
        head.next = null
        return head

    }

    //求中间的节点
    let slow = head;
    let fast = head;
    while (fast !== tail) {
        slow = slow.next
        fast = fast.next
        //快指针走两步，慢指针走一步，快指针走完，则慢指针走一半，即中间节点
        if (fast !== tail) {
            fast = fast.next
        }
    }
    // const mid = slow
    return mergeTwoLists(toSortList(head, slow), toSortList(slow, tail))
}


//利用合并两个有序链表的方式
var mergeTwoLists = function (list1, list2) {

    if (list1 == null) {
        return list2
    }
    if (list2 == null) {
        return list1
    }

    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2)
        return list1
    } else {
        list2.next = mergeTwoLists(list2.next, list1)
        return list2
    }

};
